﻿namespace LeetCodeProject._0001_1000._001_100._41_50._046;

public class Solution
{
    public IList<IList<int>> Permute(int[] nums)
    {
        if (nums == null || nums.Length == 0)
        {
            return new List<IList<int>>(0);
        }

        var lst = new LinkedList<int>();
        lst.AddLast(0);
        foreach (var n in nums)
        {
            lst.AddLast(n);
        }

        var count = 1;
        for (int i = 0; i < nums.Length; i++)
        {
            count *= i;
        }

        var result = new List<IList<int>>(count);
        Permute(lst, new int[nums.Length], 0, result);
        return result;
    }

    private void Permute(LinkedList<int> lst, int[] buff, int k, List<IList<int>> result)
    {
        if (lst.Count == 2)
        {
            buff[buff.Length - 1] = lst.Last.Value;
            result.Add((int[])buff.Clone());
            return;
        }

        var dummy = lst.First;
        var node = dummy.Next;
        while (node != null)
        {
            buff[k] = node.Value;
            lst.Remove(node);
            Permute(lst, buff, k + 1, result);
            lst.AddAfter(dummy, node);
            dummy = node;
            node = node.Next;
        }
    }
}